package _dp_base;

import java.util.Arrays;

/**
 * 740. 删除并获得点数
 */
public class No740 {
    private int[] nums;
    private int[] cache;

    /**
     * 1. 递归
     */
    public int deleteAndEarn1(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        cache = new int[n];
        Arrays.fill(cache, -1);
        Arrays.sort(nums);
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        if (cache[i] != -1) return cache[i];
        int j = 0;
        for (; j <= i; j++) {
            if (nums[j] == nums[i]) {
                break;
            }
        }
        int x = j;
        for (int k = 0; k < i; k++) {
            if (nums[k] == nums[i] - 1) {
                x = k;
                break;
            }
        }
        return cache[i] = Math.max(dfs(j - 1), dfs(x - 1) + nums[i] * (i - j + 1));
    }

    /**
     * 2. 迭代
     */
    public int deleteAndEarn2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        int[] f = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int j = 0;
            for (; j <= i; j++) {
                if (nums[j] == nums[i]) {
                    break;
                }
            }
            int x = j;
            for (int k = 0; k < i; k++) {
                if (nums[k] == nums[i] - 1) {
                    x = k;
                    break;
                }
            }
            f[i + 1] = Math.max(f[j], f[x] + nums[i] * (i - j + 1));
        }
        return f[n];
    }
}
